#include "../comm.h"
class Solution {
public:
    string smallestBeautifulString(string s, int k) {
        bool have_ans = false;
        int idx = -1;
        char ed = char('a' + k - 1);
        for(int i = s.size() - 1; i >= 0; --i)
        {
            char& ch = s[i];
            if(ch >= ed) continue;
            // char ed = char('a' + k - 1);
            char s1 = i - 1 < s.size() ? s[i - 1] : 0;
            char s2 = i - 2 >= 0 ? s[i - 2] : 0;
            for(char t = ch + 1; t <= ed; ++t)
                if(t != s1 && t != s2)
                {
                    ch = t;
                    have_ans = true;
                    idx = i;
                    break;
                }
            if(have_ans) break;
        }
        if(have_ans){
            for(int i = idx + 1; i < s.size(); ++i)
            {
                char s1 = s[i - 1], s2 = i - 2 >= 0 ? s[i - 2] : 0;
                for(int ch = 'a'; ch <= ed; ++ch)
                    if(ch != s1 && ch != s2)
                    {
                        s[i] = ch;
                        break;
                    }
            }
            return s;
        }
        else return "";
    }
};